package 普通数组

/*
41. 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：
输入：nums = [1,2,0]
输出：3

示例 2：
输入：nums = [3,4,-1,1]
输出：2

示例 3：
输入：nums = [7,8,9,11,12]
输出：1

思路:
可以理解为:
由于题目要求只能使用常数级别的空间,

  - 要找的数一定是在[1,N+1]里的整数;
    所以可以把原始的数组当作哈希表来使用, 事实上哈希表本身也是一个数组,
    要找的数就在1到N+1左闭右闭区间的整数里.

    最后的这个数N+1其实不用找, 在前N个元素都找不到的情况下, 返回N+1
    可以把1放在下标为0的位置上, 把2放在下标为1的位置上
    然后再次遍历数组, 第一个 nums[i] != i+1的位置,就是缺失的第一个数字

    例如: 输入数组  [3,4,-1,1]
    遍历数组,
    到下标0位置, 第0个元素3, 应该放在下标为2的位置, 那么两个位置进行交换
    效果: [-1,4,3,1]
    继续这个流程, 第0位的数字是-1, -1是不在1-4范围区间的, 所以放在哪里都不合适, 进入下一轮循环

    到了下标1位置, 下标为1的元素是4, 应该放在下标为3位置, 进行元素交换,
    效果: [-1,1,3,4]
    那么当前位置被交换过来的数字为1, 1应该被放在下标为0的位置, 进行交换
    效果: [1,-1,3,4]
    那么当前位置为-1, -1不在1-4范围内, 进入下一轮循环

    到了下标2位置, 3确实符合 nums[i] = i+1的标准,进入下层循环
    到了下标3位置, 4确实符合 nums[i] = i+1的标准,进入下层循环

    遍历调整位置结束后, 从头再遍历依次数组即可, 第一个不符合nums[i] = i+1的位置, 就是结果
*/
func firstMissingPositive(nums []int) int {
	n := len(nums) //获取长度

	for i := 0; i < n; i++ { //遍历元素
		//只要当前元素在0~n范围内 && 当前位置存储的元素不符合 nums[i] = i+1,那么持续将当前元素放到它应该在的下标位置
		for nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i] {
			nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
		}
	}

	for i := 0; i < n; i++ { //重新遍历一次数组
		if nums[i] != i+1 { //只要当前位置,存储的不是i+1那么就返回缺失的i+1
			return i + 1
		}
	}

	return n + 1
}
